package day_2022_12_to_3.year2023;

import java.util.*;

/**
 * @author haomin
 * @date 2023/03/07 22:56
 **/
public class Day3_7_Num1096 {
    class Solution {
        public List<String> braceExpansionII(String expression) {
            List<String> ans = dfs(expression);
            Set<String> set = new HashSet<>();
            List<String> l = new ArrayList<>();
            for(String s: ans){
                if(set.contains(s)){
                    continue;
                }
                set.add(s);
                l.add(s);
            }
            Collections.sort(l);
            return l;
        }

        private List<String> mul(List<String> a, List<String> b){
            List<String> ans = new ArrayList<>();
            for(String t : a){
                for(String n: b){
                    ans.add(t+n);
                }
            }
            return ans;
        }
        private List<String> dfs(String expression){
            List<String> ans = new ArrayList<>();

            char[] cs = expression.toCharArray();
            if(!expression.contains("{") && !expression.contains(",")){
                ans.add(expression);
                return ans;
            }
            int n = cs.length;
            for(int i=0; i<n; i++){
                if(cs[i]=='{'){
                    int cnt = 1, loc = i+1;
                    StringBuilder sb = new StringBuilder();
                    while(loc<n){
                        if(cs[loc]=='}' && cnt==1){
                            break;
                        }
                        if(cs[loc] == '{'){
                            cnt++;
                        }
                        if(cs[loc] == '}'){
                            cnt--;
                        }
                        sb.append(cs[loc++]);
                    }
                    List<String> list = braceExpansionII(sb.toString());
                    if(i==0 || cs[i-1]==','){
                        ans.addAll(list);
                    }else{
                        ans = mul(ans,list);
                    }
                    i = loc;

                }else if(cs[i]==','){

                    ans.addAll(braceExpansionII(expression.substring(i+1,n)));
                    i=n-1;

                }else{
                    StringBuilder sb = new StringBuilder();
                    int loc = i;
                    while(loc<n&&Character.isLowerCase(cs[loc])){
                        sb.append(cs[loc++]);
                    }
                    List<String> a = new ArrayList<>();
                    if(loc==n || cs[loc]==','){
                        if(i==0 || cs[i-1] == ','){
                            a.add(sb.toString());
                            ans.addAll(a);
                        }else{
                            a.add(sb.toString());
                            ans = mul(ans, a);
                        }
                        if(loc!=n){
                            ans.addAll(braceExpansionII(expression.substring(loc+1,n)));
                        }

                        i = n;
                    }else{
                        int cnt = 1;
                        loc++;
                        StringBuilder sbIn = new StringBuilder();
                        while(loc<n){
                            if(cs[loc]=='}' && cnt==1){
                                break;
                            }
                            if(cs[loc] == '{'){
                                cnt++;
                            }
                            if(cs[loc] == '}'){
                                cnt--;
                            }
                            sbIn.append(cs[loc++]);
                        }
                        List<String> list = braceExpansionII(sbIn.toString());
                        a.add(sb.toString());
                        a = mul(a, list);
                        if(i==0 || cs[i-1] == ','){
                            ans.addAll(a);
                        }else{
                            ans = mul(ans, a);
                        }
                        i = loc;
                    }
                }
            }
            return ans;
        }
    }
}